package LinkedList;

public class LinkedList<E> {

    private class Node{

        private E e;

        private Node next;

        public Node(){
            this(null,null);
        }

        public Node(E e){
            this(null,e);
        }

        public Node(Node next,E e){
            this.next = next;
            this.e = e;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyhead;

    private int size;

    public LinkedList(){
        dummyhead = new Node();
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void addFirst(E e){
      add(e,0);
    }



    public void add(E e,int index){
        if(index<0 || index>size){
            throw new IllegalArgumentException("add failed,because index<0||index>size ");
        }
        Node prev = dummyhead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = new Node(prev.next,e);
        size++;
    }

    public void addLast(E e){
        add(e,size);
    }

    public E get(int index){
        if(index<0 || index>size){
            throw new IllegalArgumentException("add failed,because index<0||index>size ");
        }
        Node cur = dummyhead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    public E getFirst(){
        return get(0);
    }

    public E getLast(){
        return get(size-1);
    }

    public void set(E e,int index){
        if(index<0 || index>size){
            throw new IllegalArgumentException("add failed,because index<0||index>size ");
        }
        Node cur = dummyhead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }


    public boolean contains(E e){
        Node cur = dummyhead.next;
        for (int i = 0; i < size; i++) {
            if(cur.e.equals(e)){
                return true;
            }else{
                cur = cur.next;
            }
        }
        return false;
    }


    public int getIndex(E e){
        Node cur = dummyhead.next;
        for (int i = 0; i < size; i++) {
            if(cur.e.equals(e)){
                return i;
            }else{
                cur = cur.next;
            }
        }
        return -1;
    }

    public E remove(int index){
        Node prev = dummyhead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node cur = prev.next;
        prev.next = cur.next;
        cur.next = null;
        size --;
        return cur.e;
    }

    public void loopRemove(E e){
        Node prev = dummyhead;
        while(prev.next!=null){
            if(prev.next.e.equals(e)){
               prev.next = prev.next.next;
            }else{
                prev = prev.next;
            }
        }
//        for(cur = prev.next;cur!=null;cur=cur.next)
//            if(cur.e.equals(e)){
//                prev.next = cur.next;
//                cur = cur.next;
//                size --;
//            }
    }

    public E removeFirst(){
        return remove(0);
    }

    public E removeLast(){
        return remove(size - 1);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for(Node cur = dummyhead.next;cur!=null;cur=cur.next)
            sb.append(cur + "->");

        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }
        linkedList.add(100,5);
        System.out.println(linkedList);
        System.out.println(linkedList.contains(6));
        linkedList.set(300,2);
        System.out.println(linkedList);
        System.out.println(linkedList.get(3));
        System.out.println(linkedList.getIndex(0));
        System.out.println("FIRST:"+linkedList.removeFirst());
        System.out.println(linkedList);
        System.out.println("LAST:"+linkedList.removeLast());
        System.out.println(linkedList);
        System.out.println(linkedList.remove(2));
        System.out.println(linkedList);
        for (int i = 5; i < 10; i++) {
            linkedList.addLast(i);
            System.out.println(linkedList);
        }
    }
}
